package cn.corffen.test.algorithm.java;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class DivideConquerJava {


    HashMap<String, List<Integer>> map = new HashMap<>();

    public List<Integer> diffWaysToCompute(String input) {
        if (input == null || input.length() == 0) {
            return new ArrayList<>();
        }
        if (map.containsKey(input)) {
            return map.get(input);
        }
        List<Integer> result = new ArrayList<>();
        int num = 0, index = 0;
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (!isOperation(c)) {
                num = 10 * num + (c - '0');
                index++;
            }
        }
        if (index == input.length()) {
            result.add(num);
            map.put(input, result);
            return result;
        }

        for (int i = 0; i < input.length(); i++) {
            if (isOperation(input.charAt(i))) {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (Integer l : left) {
                    for (Integer r : right) {
                        char op = input.charAt(i);
                        result.add(calculate(l, op, r));
                    }
                }
            }
        }
        map.put(input, result);
        return result;
    }

    private boolean isOperation(char c) {
        if (c == '+' || c == '-' || c == '*') {
            return true;
        }
        return false;
    }

    private int calculate(int left, char c, int right) {
        if (c == '+') {
            return left + right;
        } else if (c == '-') {
            return left - right;
        } else if (c == '*') {
            return left * right;
        } else {
            return -1;
        }
    }
}
